package com.duoduo.树;

import com.duoduo.TreeNode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * @program: algorithm
 * @description: 二叉树的层序遍历102
 * 给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。
 *
 *  
 *
 * 示例 1：
 *
 *
 * 输入：root = [3,9,20,null,null,15,7]
 * 输出：[[3],[9,20],[15,7]]
 *
 * @author: chaidl  ！
 * @create: 2022-05-21 22:35
 */
public class 二叉树的层序遍历102 {
	//采用队列，BFS
	public List<List<Integer>> levelOrder(TreeNode root) {
		//	定义一个队列
		List<List<Integer>> result = new ArrayList<>();
		Queue<TreeNode> queue = new LinkedList<>();
		if (root == null) {
			return result;
		}
		//从根节点开始，一次放入队列
		queue.offer(root);
		while (!queue.isEmpty()) {
			List<Integer> tmpList = new ArrayList<>();
			int size = queue.size();
			for (int i = 0; i < size; i++) {
				if (queue.peek().left != null) {
					queue.offer(queue.peek().left);
				}
				if (queue.peek().right != null) {
					queue.offer(queue.peek().right);
				}
				tmpList.add(queue.poll().val);
			}
			result.add(tmpList);
		}
		return result;
	}
}
